package algebra.query.indexing;

//import algebra.query.OrderingDescription;
import java.util.HashSet;
import java.util.Set;

import algebra.query.od.OrderDep;
import utils.exception.CoreReasoningException;
import utils.exception.OrderingDescriptionException;
import entities.assertion.ConceptAssertion;

public class TreeUtils {
	private static boolean new_depth;
	
	//the input is the root of the (sub)tree
	public static IndexTreeNode tree_to_vine(IndexTreeNode root){
		IndexTreeNode p;
		if(root == null){
			return null;
		}
		p = root;
		while(p.getLeft() != null){
			p = p.getLeft();
		}
		//q is the future parent of p (the left child of q later)
		while(true){
			IndexTreeNode q = p.getRight();
			//if p does not have right child, done.
			//otherwise, get p's right child and do a left rotation at p
			if(!p.thread){
				while(q.getLeft()!=null){
					q = q.getLeft();
				}
				p.thread = true;
				p.link.set(1, q);
			}
			if(q == null){
				break;
			}
			q.link.set(0, p);
			p = q;
		}
		//set p as the new root
		return p;
	}
	
//	private static Set<IndexTreeNode> note = new HashSet<IndexTreeNode>();
	//re-balance: right rotation, 
	//(top level) non-threaded node: nt times; i.e., how many rotations without thread adjustment
	//other threaded node: t times; i.e., how many rotations that need thread adjustment
	private static IndexTreeNode vine_compress(IndexTreeNode root, int nt, int t){
		IndexTreeNode p = root;
		//for restoring the actual root to be returned, must be the FIRST black
		IndexTreeNode temp = root; 
		boolean ndone = false;
		while(--nt >= 0){
			IndexTreeNode red = p;
			IndexTreeNode black = red.getLeft();
			if(!ndone){
				temp = black;
			}else{
				root.link.set(0, black);
			}
			ndone = true;
			red.link.set(0, black.getRight());
			black.link.set(1, red);
			root = black;
			p = black.getLeft();
		}
//		temp = root;
		boolean first = true;
		while(--t >= 0){
			IndexTreeNode red = p;
			IndexTreeNode black = red.getLeft();
			red.link.set(0, null);
			black.thread = false;
			if(first && !ndone){
				temp = black;
				first = false;
			}else{
				root.link.set(0, black);
			}
			root = black;
			p = black.getLeft();
		}
		root = temp;
		return root;
	}
	
	public static IndexTreeNode vine_to_tree(IndexTreeNode root, int treesize){
		int vine, leaves;//vines: # nodes in main vine; leaves: nodes in incomplete bottom level
		int height;
		IndexTreeNode newroot = root;
		//calculate leaves
		leaves = treesize + 1;
		while(true){
			int next = leaves & (leaves - 1);
			if(next == 0){
				break;
			}
			leaves = next;
		}
		leaves = treesize + 1 - leaves; //num of folds to do
		//reduce vine general case to special case. After folding, root is the first black!
		newroot = vine_compress(newroot, 0, leaves);
		//make special case vine into balanced tree and count height
		vine = treesize - leaves;
		height = 1 + (leaves>0? 1:0);
		if(vine > 1){
			int nonleaves = vine / 2;
			leaves /= 2;
			if(leaves > nonleaves){
				leaves = nonleaves;
				nonleaves = 0;
			}else{
				nonleaves -= leaves;
			}
			newroot = vine_compress(newroot, leaves, nonleaves);
			vine /= 2;
			height ++;
		}
		//all remaining compression use only rotations without thread adjustment
		while(vine > 1){
			newroot = vine_compress(newroot, vine/2, 0);
			vine /= 2;
			height ++;
		}
//		System.err.println("balanced tree height: "+height);
		return newroot;
	}

	private static IndexTreeNode single_rotate(IndexTreeNode tree, int dir) {
		int not_dir = dir == 0 ? 1 : 0;
		IndexTreeNode save = tree.link.get(dir);
		if(save.thread){
			System.err.println("get a thread: "+ save);
		}
		IndexTreeNode savesub = save.link.get(not_dir);
		tree.link.set(dir, savesub);
		save.link.set(not_dir, tree);
		//for threading
//		if(dir == 0){
//			if(savesub.thread){
//				savesub.link.set(1, tree);
//			}
//		}
		return save;
	}
	

	//dir-rotate at X's dir child and then not-dir-rotate at X (double dir rotation)
	private static IndexTreeNode double_rotate(IndexTreeNode tree, int dir) {
		int not_dir = dir == 0 ? 1 : 0;
//		IndexTreeNode save = tree.link.get(dir).link.get(not_dir);
//		tree.link.get(dir).link.set(not_dir, save.link.get(dir));
//		save.link.set(dir, tree.link.get(dir));
//		tree.link.set(dir, save);
////		save = tree.link.get(dir);
//		tree.link.set(dir, save.link.get(not_dir));
//		save.link.set(not_dir, tree);
//		return save;
		IndexTreeNode sub = tree.link.get(dir);
		IndexTreeNode ret = single_rotate(sub, dir);
		tree.link.set(dir, ret);
		ret = single_rotate(tree, not_dir);
		return ret;
	}

	private static void fix_balance_factors(IndexTreeNode tree, int dir) {
		int not_dir = dir == 0 ? 1 : 0;

		if (tree.link.get(dir).link.get(not_dir).balance == dir) {
			tree.balance = 2;
			tree.link.get(dir).balance = not_dir;
		} else if (tree.link.get(dir).link.get(not_dir).balance == not_dir) {
			tree.balance = dir;
			tree.link.get(dir).balance = 2;
		} else {
			tree.balance = tree.link.get(dir).balance = 2;
		}
		tree.link.get(dir).link.get(not_dir).balance = 2;
	}

//	private static IndexTreeNode rebalance_insert(IndexTreeNode tree, int dir) {
//
//		int not_dir = dir == 0 ? 1 : 0;
//		if (tree.balance == dir) {
//			if (tree.link.get(dir).balance == dir) {
//				tree.link.get(dir).balance = 2;
//				tree.balance = 2;
//				tree = single_rotate(tree, dir);
//			} else {
//				fix_balance_factors(tree, dir);
//				tree = double_rotate(tree, dir);
//			}
//			new_depth = false;
//		} else if (tree.balance == not_dir) {
//			tree.balance = 2;
//			new_depth = false;
//		} else {
//			tree.balance = dir;
//			//a safe node is now a root, threading to be handled here
//			if(tree.thread && tree.getRight()!= null){
//				tree.thread = false;
//			}
//		}
//		return tree;
//	}

	private static IndexTreeNode rebalance_remove(IndexTreeNode tree, int dir) {

		int not_dir = dir == 0 ? 1 : 0;

		if (tree.balance == dir) {
			tree.balance = 2;
		} else if (tree.balance == not_dir) {
			if (tree.link.get(not_dir).balance == not_dir) {
				tree.link.get(not_dir).balance = 2;
				tree.balance = 2;
				tree = single_rotate(tree, not_dir);
			} else if (tree.link.get(not_dir).balance == 2) {
				tree.link.get(not_dir).balance = dir;
				tree = single_rotate(tree, not_dir);
			} else {
				fix_balance_factors(tree, not_dir);
				tree = double_rotate(tree, not_dir);
			}
			new_depth = false;
		} else {
			tree.balance = not_dir;
			new_depth = false;
		}
		return tree;
	}

//	private static IndexTreeNode insert_r(IndexTreeNode node, OrderDep od,
//			ConceptAssertion ca) throws OrderingDescriptionException,
//			CoreReasoningException {
//		if (node == null) {
//			node = new IndexTreeNode(ca);
//			new_depth = true;
//		} else {
//			System.err.println("compare "+ca + " with given node "+node.getNodeAssertion());
//			int dir = od.compare(ca, node.getNodeAssertion());
//			dir = dir > 0 ? 1 : 0;
////			node.link.set(dir, insert(node.link.get(dir), od, ca));
//			if(dir == 0){
//				 //insert left node
//				 IndexTreeNode left = insert(node.getLeft(), od, ca);
//				 node.link.set(0, left);
//				 //add thread for the new node
//				 left.link.set(1, node);
//			}else if(dir == 1){
//				//insert right node
//				 IndexTreeNode right = insert(node.getRight(), od, ca);
//				 node.link.set(1, right);
//				 //shift the old thread down to the new node
//				 if(node.thread){
//					 right.link.set(1, node.getRight());
//					 right.thread = false;
//				 }else{
//					 node.thread = false;
//				 }
//			 }
//			//
//			if (new_depth) {
//				node = rebalance_insert(node, dir);
//			}
//		}
//		return node;
//	}
	
	private static int getDir(ConceptAssertion l, ConceptAssertion r, OrderDep od){
		//insert l, first compare it with r
		int dir = 0;
		try {
			if(r.getConcept().isTop() || l.getConcept().isTop()){
				dir = 0;
			}else{
				dir = od.compare(l, r);
			}
		} catch (Exception e) {
			e.printStackTrace();
		} 
		if(dir >= 1){
			return dir;
		}else if(dir <= -1){
			return 0;
		}else if(dir == 0){
			//randomly inserted as left or right element
//			dir = (new java.util.Random().nextBoolean()? 1:0);
			dir = 0;
		}
		return dir;
	}
	
	//a version that follows knuth 1997
	public static IndexTreeNode insert(IndexTreeNode root, OrderDep od,
			ConceptAssertion ca) throws OrderingDescriptionException,
			CoreReasoningException {
		IndexTreeNode p; //current node in search
		IndexTreeNode n; //new node;
		int dir;
		//search for an insertion point
		if(root != null){
			for(p = root;;p = p.link.get(dir)){
				dir = getDir(ca, p.getNodeAssertion(), od);
				if(dir == 0 && p.getLeft() == null){
					break;
				}else if(dir == 1 && p.thread){
					break;
				}
			}
		}else{
			p = root;
			dir = 0;
		}
		//insertion below
		n = new IndexTreeNode(ca);
//		if(ca.getIndividual().toString().contains("Casio_Exilim_EX-ZR100_inst")){
//			System.out.println("stop");
//		}
		n.link.set(0, null);
		if(dir == 0){
			if(root != null){
				n.link.set(1, p);
			}else{
				n.link.set(1, null);
			}
		}else if(dir == 1){
			//insert right node
			p.thread = false;
			n.link.set(1, p.getRight());
		}
		p.link.set(dir, n);
		return root;
	}
	
	
//	public static IndexTreeNode insert(IndexTreeNode node, OrderDep od,
//			ConceptAssertion ca) throws OrderingDescriptionException,
//			CoreReasoningException {
////		if (node == null) {
////			node = new IndexTreeNode(ca);
////			new_depth = true;
////		} else {
//			int dir;
////			if(ca.toString().contains("Fujifilm_X10_inst")){
////				System.err.println(" ");
////			}
//			while(true){
//				dir = od.compare(ca, node.getNodeAssertion());
//				dir = dir > 0 ? 1 : 0;
//				if(dir == 1 && node.thread){
//					break;
//				}else if(node.link.get(dir) == null){
//					break;
//				}
//				node = node.link.get(dir);
//			}
//			IndexTreeNode toadd = new IndexTreeNode(ca);
////			IndexTreeNode toadd = insert(node.link.get(dir), od, ca);
//			if(dir == 0){
//				 //add thread for the new node
//				toadd.link.set(1, node);
//			}else if(dir == 1){
//				//insert right node
//				node.thread = false;
//				toadd.link.set(1, node.getRight());
//			}
//			node.link.set(dir, toadd);
//			//
////			if (new_depth) {
////				node = rebalance_insert(node, dir);
////			}
////		}
//		return node;
//	}

//	private static IndexTreeNode insert_wo_rotation(IndexTreeNode tree,
//			OrderDep od, ConceptAssertion ca)
//			throws OrderingDescriptionException, CoreReasoningException {
//		if (tree == null) {
//			tree = new IndexTreeNode(ca);
//		} else {
//			int dir = od.compare(ca, tree.getNodeAssertion());
//			if (dir < -1) {
//				System.out.println(dir);
//			}
//			dir = dir > 0 ? 1 : 0;
//			tree.link.set(dir, insert_wo_rotation(tree.link.get(dir), od, ca));
//		}
//		return tree;
//	}

	private static IndexTreeNode remove_r(IndexTreeNode tree, OrderDep od,
			ConceptAssertion data) throws OrderingDescriptionException,
			CoreReasoningException {
		if (tree == null) {
			new_depth = false;
		} else if (od.compare(data, tree.getNodeAssertion()) == 0) {
			if (tree.link.get(0) != null && tree.link.get(1) != null) {
				IndexTreeNode heir = tree.link.get(0);
				while (heir.link.get(1) != null) {
					heir = heir.link.get(1);
				}
				tree.data = heir.data;
				tree.link
						.set(0,
								remove_r(tree.link.get(0), od,
										tree.getNodeAssertion()));
				if (new_depth) {
					tree = rebalance_remove(tree, 0);
				}
			} else {
				// AVLNode<T> save = tree;
				tree = tree.link.get(tree.link.get(0) == null ? 1 : 0);
				new_depth = true;
			}
		} else {
			int dir = od.compare(data, tree.getNodeAssertion()) > 0 ? 1 : 0;
			// int dir = data.compareTo(tree.data) > 0 ? 1 : 0;
			tree.link.set(dir, remove_r(tree.link.get(dir), od, data));
			if (new_depth) {
				tree = rebalance_remove(tree, dir);
			}
		}
		return tree;
	}

	// return the node just inserted
//	public static IndexTreeNode insert(IndexTreeNode tree, OrderDep od,
//			ConceptAssertion ca) throws OrderingDescriptionException,
//			CoreReasoningException {
//		new_depth = false;
//		return insert_r(tree, od, ca);
//		// return insert_wo_rotation(tree, od, ca);
//	}

	public static IndexTreeNode remove(IndexTreeNode tree, OrderDep od,
			ConceptAssertion data) throws OrderingDescriptionException,
			CoreReasoningException {
		new_depth = false;
		return remove_r(tree, od, data);
	}

	public static void structure(IndexTreeNode tree, int level) {
		int i;
		if (tree == null) {
			for (i = 0; i < level; i++) {
				System.out.print("\t");
			}
			System.out.println();
			return;
		}
		structure(tree.link.get(1), level + 1);
		for (i = 0; i < level; i++) {
			System.out.print("\t");
		}
		System.out.println(tree.data + "(" + tree.balance + ")");
		structure(tree.link.get(0), level + 1);
	}

}
